from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        n = len(matrix)
        if n <= 0:
            return []
        m = len(matrix[0])
        sp = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        x, y, d, t = 0, 0, 0, 0
        ans = []
        # status = [[0] * m] * n  # 外面这层这种方式是引用 ？？？
        status = [[0]*m for i in range(n)]
        while t < n*m:
            ans.append(matrix[x][y])
            status[x][y] = 1
            t += 1
            if t >= n*m:
                break
            xx, yy = x + sp[d][0], y + sp[d][1]
            if xx < 0 or xx >= n or yy < 0 or yy >= m or status[xx][yy] == 1:
                d = (d + 1) % 4
                xx, yy = x + sp[d][0], y + sp[d][1]
            x, y = xx, yy
        return ans


s = Solution()
mm = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

print(mm)
print(s.spiralOrder(mm))
